//
// Created by EDZ on 2022/2/9.
//

#ifndef INC_2022_1_STRMATCH_H
#define INC_2022_1_STRMATCH_H
#include "../head/common.h"

using namespace std;

/**
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param haystack
 * @param needle
 * @return
 */
int strStr(string haystack, string needle) {
    cout<<haystack.find(needle);
    return 0;
}


/**
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subtree-of-another-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param root
 * @param subRoot
 * @return
 */
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if(root==NULL&&subRoot==NULL)
    if(root->left!=NULL&&root->right!=NULL&&subRoot->left!=NULL&&subRoot->right!=NULL&&root->val==subRoot->val){
        return true;
    }
    if(root&&subRoot){
        return isSubtree(root->left,subRoot->left)&&isSubtree(root->right,subRoot->right) ||
                    (isSubtree(root->right,subRoot)||isSubtree(root->left,subRoot));
    }
    return false;
}

/**
 * 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
 * @param s1
 * @param s2
 * @return
 */
bool isFlipedString(string s1, string s2) {
    return s1.size()==s2.size() && (s2+s2).find(s1)!= string::npos;
}

vector<int> getNextVal(string s){
    vector<int> nextVal(s.size());
    nextVal[0] = -1;
    int i = 0,j = -1;
    int len = s.size();
    while(i<len-1){
        if(j==-1||s[i]==s[j]){
            i++;
            j++;
            nextVal[i] = j;
        }else{
            j = nextVal[j];
        }
    }
    return nextVal;
}

int KMP_1(string s1,string s2){
    vector<int> nextVal = getNextVal(s2);
    int i = 0,j = 0;
    int len1 = s1.size(),len2 = s2.size();
    while(i<len1&&j<len2){
        if(s1[i]==s2[j]||j==-1){
            i++;
            j++;
        }else{
            j = nextVal[j];
        }
    }
    if(j>=len2){
        return (i-len2+1);
    }else{
        return -1;
    }
}















#endif //INC_2022_1_STRMATCH_H
